from copy import deepcopy
from collections import defaultdict


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        s_dic = {}
        for word in s:
            if word in s_dic:
                s_dic[word] += 1
            else:
                s_dic[word] = 1
        for word in t:
            try:
                s_dic[word] -= 1
                if s_dic[word] < 0:
                    return ""
            except:
                return ""
        i, j = 0, len(s) - 1
        while True:
            if s[i] in t:
                if s_dic[s[i]] > 0:
                    s_dic[s[i]] -= 1
                else:
                    break
            i += 1
        while True:
            if s[j] in t:
                if s_dic[s[j]] > 0:
                    s_dic[s[j]] -= 1
                else:
                    break
            j -= 1
        print(i, j)
        return s[i:j + 1]

    def minWindow2(self, s: str, t: str) -> str:
        t_dic = {}
        for word in t:
            if word in t_dic:
                t_dic[word] -= 1
            else:t_dic[word] = -1
        silp_include = [deepcopy(t_dic) for i in range(0, len(s))]
        # print(len(silp_include))
        for len_silp in range(1, len(s) + 1):
            # print(silp_include[9])
            for silp_start in range(0, len(s) - len_silp + 1):
                word = s[silp_start+len_silp-1]
                mid_dic = silp_include[silp_start]
                if word in mid_dic:
                    mid_dic[word] += 1
                    if mid_dic[word] >= 0:
                        mid_dic.pop(word)
                        if len(mid_dic) == 0:
                            # print(silp_include)
                            return s[silp_start:silp_start+len_silp]

    def minWindow3(self, s: str, t: str) -> str:
        j, res, flag = -1, s, False
        while True:
            t_list = list(t)
            while j < len(s) - 1:
                j += 1
                if s[j] in t_list:
                    t_list.remove(s[j])
                    if len(t_list) == 0:
                        flag = True
                        break
            if not flag:
                return ""
            t_list, i = list(t), j+1
            while True:
                i -= 1
                if s[i] in t_list:
                    t_list.remove(s[i])
                    if len(t_list) == 0:
                        break
            if len(res) > j - i:
                res = s[i:j+1]
            if j >= len(s) - 1:
                break
            j = i
        return res

    def minWindow4(self, s: str, t: str) -> str:
        i, res, flag = 0, s, False
        t_len = len(t)
        t_dic = defaultdict(int)
        for word in t:
            t_dic[word] += 1
        for index, j in enumerate(s):
            if j in t:
                if t_dic[j] > 0:
                    t_len -= 1
                t_dic[j] -= 1
                if t_len == 0:
                    flag = True
                    while (s[i] not in t) or (t_dic[s[i]] < 0):
                        if s[i] in t:
                            t_dic[s[i]] += 1
                        i += 1
                    if index - i < len(res):
                        res = s[i:index + 1]
                    t_dic[s[i]] += 1
                    i += 1
                    t_len += 1
        if not flag:
            return ""
        else:
            return res


a = Solution()
print(a.minWindow4(s="ADOBECODEBANC", t="ABC"))
print(a.minWindow4(s="ADOBECODEBANC", t="ABCadsafdf"))
print(a.minWindow4("cabwefgewcwaefgcf", "cae"))
